package org.usmile.algorithms.learn.trie;

import java.util.HashMap;
import java.util.Map;

public class MapTrie {
    Node root;

    public MapTrie() {
        this.root = new Node();
    }

    private static class Node {
        Map<Character, Node> children;

        boolean isWord;

        public Node() {
            this.children = new HashMap<>();
            this.isWord = false;
        }

        public boolean childrenContainsChar(Character c) {
            return children.containsKey(c);
        }
    }

    public void add(String word) {
        Node curr = root;
        for (Character c : word.toCharArray()) {
            if (!curr.childrenContainsChar(c)) {
                curr.children.put(c, new Node());
            }
            curr = curr.children.get(c);
        }

        curr.isWord = true;
    }


    public boolean contains(String word) {
        Node curr = root;
        for (Character c : word.toCharArray()) {
            if (!curr.children.containsKey(c)) {
                return false;
            }
            curr = curr.children.get(c);
        }

        return curr.isWord;
    }

    public static void main(String[] args) {
        MapTrie arrayTrie = new MapTrie();
        arrayTrie.add("Hello");
        arrayTrie.add("World");

        System.out.println(arrayTrie.contains("Hello"));
        System.out.println(arrayTrie.contains("xx"));
    }
}
